package com.fmm.medium;

public class ChargeCoin {

    /**
     * @param coins 硬币的种类
     * @param amount 总额
     * @return 返回达到总额所使用的硬币的最少数量，如果无法达到总额，返回-1
     * */
    public static int coinChange(int[] coins, int amount) {
        return coinChange(coins, amount, new int[amount]);
    }

    /**
     * @param coins 硬币的种类
     * @param amount 总额
     * @param cache 缓存，使用 coins 达到 "索引" 总额的最少数量。例如 cache[100]，表示达到 100 最少需要多少硬币
     * @return 返回达到总额所使用的硬币的最少数量，如果无法达到总额，返回-1
     * */
    private static int coinChange(int[] coins, int amount, int[] cache) {
        if (amount == 0) {
            return 0;
        }
        // 缓存加速，如果有缓存直接返回
        if (cache[amount - 1] != 0) {
            return cache[amount - 1];
        }
        int result = Integer.MAX_VALUE;
        for (int coin : coins) {
            // 如果总额比银币值都小，表示无法达到
            if (amount >= coin) {
                // 递归求解子问题，得到子问题的结果
                int subResult = coinChange(coins, amount - coin, cache);
                // 如果子问题无解，无需关心最优值
                if (subResult >= 0) {
                    // 子问题有解，更新最优结果
                    result = Math.min(result, subResult + 1);
                }
            }
        }
        // 返回结果
        int r = result == Integer.MAX_VALUE ? -1 : result;
        // 缓存结果
        cache[amount - 1] = r;
        return r;
    }

    public static void main(String[] args) {
        int[] coins = {186,419,83,408};
        int amount = 6249;
        System.out.println(coinChange(coins, amount));
    }
}
